package leetcode.weekly.week309;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.TreeSet;

//Solution4Test
public class Solution4 {

	public int mostBooked(int n, int[][] meetings) {
		Arrays.sort(meetings, (a, b) -> a[0] - b[0]);
		PriorityQueue<Integer> freeRoom = new PriorityQueue<>((a, b) -> a - b);
		for (int i = 0; i < n; i++) {
			freeRoom.add(i);
		}
		// 可用时间，编号
		PriorityQueue<long[]> queue = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));
		Queue<Integer> waits = new LinkedList<>();
		int[] times = new int[n];
		int m = 0;
		long curTime = 0;
		while (m < meetings.length || !waits.isEmpty()) {//
			if (!waits.isEmpty()) {
				if (freeRoom.isEmpty()) {
					long[] cur = queue.peek();
					curTime = cur[0];
					while (m < meetings.length && meetings[m][0] < curTime) {
						int[] meeting = meetings[m];
						int start = meeting[0], end = meeting[1], last = end - start;
						waits.add(last);
						m++;
					}
					while (!queue.isEmpty() && queue.peek()[0] == curTime) {
						freeRoom.add((int)queue.poll()[1]);
					}
				}
				int use = freeRoom.poll();
				times[use]++;
				queue.add(new long[] { curTime + waits.poll(), use });
			} else if (m < meetings.length) {
				int[] meeting = meetings[m];
				int start = meeting[0], end = meeting[1], last = end - start;
				while (!queue.isEmpty() && queue.peek()[0] <= start) {
					freeRoom.add((int) queue.poll()[1]);
				}
				if (freeRoom.isEmpty()) {
					waits.add(last);
				} else {
					int use = freeRoom.poll();
					times[use]++;
					queue.add(new long[] { end, use });
				}
				m++;
			}
		}
		int ansi = 0, max = 0;
		for (int i = 0; i < times.length; i++) {
			int time = times[i];
			if (time > max) {
				ansi = i;
				max = time;
			}
		}
		return ansi;
	}

}
